package LinkedList;

import java.util.Stack;

/**
 * @Author: 吕庆龙
 * @Date: 2019/9/27 15:26
 * <p>
 * 功能描述:
 */
public class SingleLinkedListTest {

    public static void main(String[] args) {
        SingleLinkedList list = new SingleLinkedList();
        Node head = list.head;
        //1.简单测试链表功能
        Node node1 = new Node(1, "吕庆龙");
        Node node2 = new Node(2, "李茜薇");
        Node node3 = new Node(3, "陈宇");
        Node node4 = new Node(4, "郑怡");
        Node node5 = new Node(5,"孙尚香");

        list.add(node1);
        list.add(node3);
        list.add(node2);
        list.add(node5);
        list.add(node4);

        list.showList();

        //2.面试题测试
        //2-1 【新浪面试题】测试
        System.out.println(getLength(head));
        System.out.println("倒数第二个节点是:" + FindNodeByLastIndex(head,2));

        System.out.println();
        System.out.println();
        System.out.println();

        //2-2 【腾讯面试题】测试
        System.out.println("----------------------反转链表测试----------------------");
        System.out.println("链表反转前-------------->");
        list.showList();
        System.out.println("链表反转后-------------->");
        reverseList(head);
        list.showList();

        System.out.println();
        System.out.println();
        System.out.println();

        //2-3 【百度面试题】测试
        System.out.println("----------------------逆序打印链表----------------------");
        reversePrint(head);

    }

    //下面是面试题,我们写成静态函数

    //统计链表节点个数
    public static Integer getLength(Node head){

        if(head.next == null){
            return 0;
        }
        Integer count = 0;
        Node temp = head.next;
        while (true){
            if (temp == null){
                break;
            }
            count++;
            temp = temp.next;
        }

        return count;
    }

    //查找单链表中的倒数第k个结点 【新浪面试题】
    public static Node FindNodeByLastIndex(Node head,Integer index){

        Integer size = getLength(head);
        if(index <= 0 || index > size){
            System.out.println("索引不合法!");
            return null;
        }

        Node temp = head.next;
        for (int i = 0; i < size - index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    //反转链表,可以用尾插法来反转 【腾讯面试题】
    public static void reverseList(Node head){
        //如果链表除了头结点没有节点或者只有一个节点,则不需要反转
        if(head.next == null|| head.next.next == null){
            System.out.println("链表除了头结点没有节点或者只有一个节点,不需要反转");
            return;
        }
        Node reverseHead = new Node(0,"反转链表的头结点");
        Node current = head.next;
        Node temp = null;
        while(current != null){
            temp = current.next;       //先把后面节点记录下来,免得丢失了
            current.next = reverseHead.next;
            reverseHead.next = current;
            current = temp;
        }
        //由于传的是引用,这里就直接改动了原链表
        head.next = reverseHead.next;
    }
/**
 * 1.逆序打印链表   【百度面试题】
 * 2.我们采用第二种方式,栈的方式
 * 3.第一种方式就是先逆序链表,再依次打印,但是此种方式会改动原有链表(不推荐)。
 * 但实际上我们可以做到不改动原有链表,就是上面的方法改一下返回值就可以了
 */

    public static void reversePrint(Node head){
        if(head.next == null){
            System.out.println("链表为空,无需逆序打印");
            return;
        }

        Stack<Node> stack = new Stack<>();
        Node current = head.next;
        //遍历链表并放入栈中
        while(current != null){
            stack.push(current);
            current = current.next;
        }
        //根据栈先进先出的特性直接遍历栈打印即是逆序打印
        while (stack.size() > 0){
            System.out.println(stack.pop());
        }
    }
}


/**
 * 功能描述: 只写几个简单的方法
 * 1.注意为什么都不能动head,因为java对于对象参数传的是引用。你如果把head节点给动了,那
 * 外边的链表就找不到了。我们需要这个head节点来定位这个链表
 */
class SingleLinkedList{
    public Node head = new Node(0,"头结点");

    /**
     * 功能描述: 往链表里添加节点(这个算是尾插法)
     */
    public void add(Node node){
        Node temp = head;  //注意为什么不能直接动head节点,因为这是传引用,你一动,就真的把外面的也变了
        while(true){
            if(temp.next == null){
                temp.next = node;
                break;
            }
            temp = temp.next;
        }
    }

    /**
     * 功能描述: 遍历所有节点
     */
    public void showList(){
        Node temp = head.next;

        if(temp == null){
            System.out.println("链表为空");
        }

        while(true){
            if(temp == null){
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }
}

class Node{
    public Integer No;
    public String Name;
    public Node next;

    public Node(Integer no, String name) {
        No = no;
        Name = name;
    }

    @Override
    public String toString() {
        return "Node{" + "No=" + No + ", Name='" + Name + '\'' + '}';
    }
}